1. Field of the Invention
This invention generally relates to data transmission and error correction systems. More particularly, it relates to an apparatus and method, for generating data error position information in response to a serial binary data stream using the Miller-squared coding rules, to increase error correction capability.
2. Description of the Prior Art
Data reliability in a digital data information transmission channel is enhanced by error detection and correction. Many error correction coding (ECC) methods are available, such as Reed-Solomon codes, Fire codes, and Hamming codes, all serving to ensure data integrity in the information channel. Data typically undergoes redundancy encoding by an ECC encoder at a transmitting end of the information channel. Prior to transmission, however, this ECC encoded data stream generally is further encoded according to a set of information channel data coding rules. Two of the common channel codes are Manchester codes and the Miller-squared (M.sup.2) code. The appropriate channel code is selected based on the nature of the information channel; for example, the Miller-squared (M.sup.2) code finds particular applicability to magnetic recording and reproducing channels because it embeds timing information into a data stream (self-clocking), the resulting code stream is direct current free and polarity insensitive. A more complete description of the Miller code and Miller-squared code may be had by reference to Miller U.S. Pat. No. Re. 31,311, dated Jul. 12, 1983 (Miller-squared or M.sup.2 code) and Miller U.S. Pat. No. 3,108,261 issued Oct. 22, 1963 (Miller code or the M code).
The Miller-squared code is such that transitions can occur either in the middle of a data cell, or at the boundary between data cells. A data cell or a bit cell refers to an interval in time identifiable by separate timing pulses (clock) containing a logical data bit. There are two M.sup.2 code bits per data bit and the M.sup.2 encoder and decoder operate at a clock frequency which is twice the serial data rate. This double rate clock is referred to as the M.sup.2 clock. There are three rules, constraints or conditions in a M.sup.2 code stream such as a playback code stream of a magnetic recorder, which can be easily checked to detect illegal M.sup.2 code sequences. These three conditions do not fully define the M.sup.2 code but are a consequence of the M.sup.2 coding rules, as defined in the U.S. Pat. No. Re. 31,311.
1. The minimum run length between transitions in M.sup.2 code is one data cell or two M.sup.2 clocks. A shorter run length than this indicates an error in the playback code stream and is referred to as a short run violation.
2. The maximum run length between transitions in M.sup.2 code is three data cells or six M.sup.2 clocks. A longer run length than this indicates an error in the playback data stream and is referred to as a long run violation.
3. Whenever a run length of two or more data cells (four or more M.sup.2 clocks) occurs, the transition beginning the run occurs in the middle of a data cell. This is referred to as an M.sup.2 sync sequence since it is used to determine the location of the data cell boundaries in the M.sup.2 decoder. If the transition occurs at the boundary of two cells it indicates an error in the playback data stream and is referred to an illegal sync sequence.
An illegal M.sup.2 sequence (or a sequence that violates a rule or constraint) is the result of an error in the playback M.sup.2 code stream which causes a transition to be shifted; however, not all playback errors result in illegal M.sup.2 sequences. When an illegal M.sup.2 sequence occurs the M.sup.2 decoder will produce an error in the decoded output data, but its location will be uncertain, generally occurring in one of two possible data bits. Thus, it is generally necessary to flag two decoded data bits as uncertain when an illegal M.sup.2 sequence is detected.
For transmission, data, including both information and error correction redundancy codes, is first encoded by a set of discrete electrical signals in accordance with the channel coding scheme, at a source terminal, and is subsequently decoded at a data receiving terminal. This channel coding scheme transforms the data and applies in addition to and independently of the error correction method used. This set of electrical signal patterns involve defining certain time relationships among the individual transmission waveforms. The source terminal transmits the individual signals using predefined time relationships so the receiving terminal can recognize each discrete signal as it arrives. These data bits may be recorded or transmitted or may otherwise be recorded on or reproduced from a magnetic tape.
In magnetic tape recording, electromagnetic interference during transmission, media dropout, poor head to tape contact, Gaussian thermal noise and tape surface contamination are sources of errors. Magnetic recording errors generally come in two kinds. There are large corruptions, called error bursts, where numerous bits are corrupted together in an area which is otherwise error free, and random errors affecting single bits. Whatever the mechanism, the result will be that the received data will not be exactly the same as those sent. Sometimes it is enough to know that there has been an error, if time allows a retransmission to be arranged. This is feasible for telex messages, but very inappropriate for others, such as audio or video transmissions.
Each error correction code (ECC) generally includes error detection and error correction functions. In any error correction method the degree of protection used should be appropriate for the probability of errors to be encountered. Since increased error correction ability generally requires greater redundancy and therefore channel bandwidth, as well as complexity, there is a tradeoff in ECC design.
In general, two pieces of independent information are necessary for elucidating two unknowns. In ECC, the position of an error and its value are critical pieces of information. If one of them, such as the error position, is somehow known from an external source, a source outside the scope of the ECC decoder, then an erred message can be corrected as to its exact content even if the other piece of information, such as correct value, is the only piece of information derivable from the ECC decoder in use.
A common ECC is a Reed-Solomon code. In a Reed-Solomon code, like various digital systems data bits are assembled into data words, or symbols. A symbol of any size is possible but a symbol size of eight bits is commonly used because it works conveniently with byte-oriented systems. Eight bit symbols implies a maximum sequence length of 2.sup.8 -1=255 symbols. This sequence of up to 255 symbols is called a code word. As each symbol contains 8 bits, the code word will be up to: 255.times.8=2040 bits long. Within the code word, a number of symbols are designated as check symbols. Each check symbol represents a level of redundancy able to provide one piece of error information, such as an error position or value. All error correction relies on adding redundancy to information for transmission.
As an illustration, a Reed Solomon code word of 255 8-bit symbols with 10 check symbols limits data to the remaining 245 symbols. Since an error correction requires two levels of redundancy or two check symbols (one each for position and value), an ECC decoder theoretically can detect and correct up to 5 errors within this code word. In some video and audio applications, it is a better strategy to simply detect the errors without correcting them; then, in that case, up to 10 errors may be detected without correction. When the position of errors is known by some other means, twice as many errors can be corrected for the same amount of redundancy. This gives the name of erasure correction. Erasure correction refers to correcting errors when their locations are known, but their values are unknown. Potentially, having erasure information can double the error correction capability.
In accordance with an aspect of the present invention, there is provided a new and improved Miller-squared decoder which enables output of a signal upon detection of a M.sup.2 rule violation, with the signal and data stream then being transmitted to the error correction circuitry.